
//122.买卖股票的最佳时机II
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //使用动态规划来实现
        //一共就两种状态
        //1. 在第i天买股票了  2. 在第i天没有买股票
        //使用两个DP表来表示两种情况在每一天中获得的最大利润

        int n = prices.size();
        vector<int> f(n) , g(n) ;
        f[0] = -prices[0] ;
        for(int i = 1; i < n ;i++)
        {
            f[i] = max(f[i-1], g[i-1] - prices[i]);
            g[i] = max(g[i-1],f[i-1] + prices[i]);
        }
        return g[n-1];
    }
};